package leetcode每日一题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 1. 问题描述
 *      给出一个区间的集合，请合并所有重叠的区间。
 *
 * 2. 算法描述
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 合并区间 {
    public static void main(String[] args) {

    }

    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if(len < 2) {
            return intervals;
        }
        Arrays.sort(intervals,(a,b)->a[0]-b[0]); // lamdba表达式
        List<int[]> temp = new ArrayList<>();
        for(int[] interval : intervals) {
            if(temp.size() == 0 || interval[0] > temp.get(temp.size()-1)[1]) {
                // 如果temp为空或者当前区间的起始边界大于temp中最后一个区间的，说明此时没有相交，直接加入即可
                temp.add(interval);
            } else {
                // 此时说明temp不空或者区间相交，所以此时我们还是需要判断当前是因为不空还是相交
                if(interval[0] <= temp.get(temp.size()-1)[1]) {
                    // 如果是相交
                    // temp中的最后一个区间[y1,y2]  当前区间[x1,x2]
                    // 合并[y1,z] z = Math.max(y2,x2)
                    int z = Math.max(interval[1],temp.get(temp.size()-1)[1]);
                    temp.get(temp.size()-1)[1] = z;
                }
            }
        }
        int[][] res = new int[temp.size()][2];
        for(int i = 0; i < temp.size(); i++) {
            res[i] = temp.get(i);
        }
        return res;
    }
}
